class Solution:
    def _combinationSum(self, candidates: 'List[int]', target: int) -> 'List[List[int]]':
        res = []
        for i in range(len(candidates)):
            # print('c target', candidates[i], target)
            # print('candidates', candidates)
            if candidates[i] == target:
                res.append([candidates[i]])
                continue
            if candidates[i] > target:
                break
            back = self._combinationSum(candidates[i:], target-candidates[i])
            for r in back:
                r.append(candidates[i])
            res.extend(back)
        return res

    def combinationSum(self, candidates: 'List[int]', target: int) -> 'List[List[int]]':
        return self._combinationSum(sorted(candidates), target)

if __name__ == "__main__":
    s = Solution()
    print(s.combinationSum([2, 3, 5], 8))
    print(s.combinationSum(candidates = [2,3,6,7], target = 7))